/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

import com.factory.server.analyser.Analyser;
import com.factory.server.dto.EdgeDTO;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Logger;
import org.jgrapht.alg.FloydWarshallShortestPaths;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedWeightedMultigraph;
import org.jgrapht.graph.GraphPathImpl;

/**
 *
 * source: http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus
 */
public class FloydWarshall {

    static final Logger LOG = Logger.getLogger(Analyser.class.getName());
    GraphProblemresult graphProblemresult;
    List<Integer> path = new ArrayList<Integer>();
    boolean pathSuccess = true;

    public GraphProblemresult execute(List<EdgeDTO> inputEdgeList, int nodesCount) {
        LOG.info("FloydWarshall started. Number of edges:" + inputEdgeList.size());
        GraphProblemresult graphProblemresult = new GraphProblemresult();
        int[][] distancesMatrix = new int[nodesCount][nodesCount];

        for (int i = 0; i < nodesCount; i++) {
            for (int j = 0; j < nodesCount; j++) {
                distancesMatrix[i][j] = i == j ? 0 : Integer.MAX_VALUE;
            }
        }

        for (EdgeDTO edgeDTO : inputEdgeList) {
            try {
                distancesMatrix[edgeDTO.getSource()][edgeDTO.getTarget()] = (int) edgeDTO.getCost();
            } catch (NullPointerException ex) {
                System.out.println("dpc");
            }
        }

        int[][] predecessors = floydWarshall(distancesMatrix);

        for (int i = 0; i < nodesCount; i++) {
            for (int j = 0; j < nodesCount; j++) {
                if (i == j) {
                    continue;
                }
                int k = j;
                while (predecessors[i][k] != -1){
                    //graphProblemresult.getShortestPath().add(new EdgeDTO(predecessors[target], target, graphDistances[predecessors[target]][target]));
                    graphProblemresult.getShortestPath().add(new EdgeDTO(predecessors[i][k], k, distancesMatrix[i][k] - distancesMatrix[i][predecessors[i][k]]));
                    k = predecessors[i][k];
                    if (k == -1 || k == i) {
                        break;
                    }
                }
                graphProblemresult.getShortestPath().add(new EdgeDTO(null, null, 0));
            }
        }
//        System.out.println(graphProblemresult.getEdges());
        return graphProblemresult;
    }

    private List<EdgeDTO> transformToEdges(List<Integer> paths, int[][] distancesMatrix) {
        List<EdgeDTO> pathEdges = new ArrayList<EdgeDTO>();
        for (int i = 1; i < paths.size(); i++) {
            pathEdges.add(new EdgeDTO(i - 1, i, distancesMatrix[i - 1][i]));
        }
        return pathEdges;
    }

    private void getPath(int[][] matrix, Integer source, Integer target) {
        if (source == target) {
            path.add(source);
        } else {
            if (matrix[source][target] == -1) {
                pathSuccess = false;
            } else {
                getPath(matrix, source, matrix[source][target]);
                path.add(target);
            }
        }
    }

    /**
     * Floyd-Warshall algorithm. Finds all shortest paths among all pairs of
     * nodes
     *
     * @param d matrix of distances (Integer.MAX_VALUE represents positive
     * infinity)
     * @return matrix of predecessors
     */
    public static int[][] floydWarshall(int[][] d) {
        int[][] p = constructInitialMatixOfPredecessors(d);
        for (int k = 0; k < d.length; k++) {
            for (int i = 0; i < d.length; i++) {
                for (int j = 0; j < d.length; j++) {
                    if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {
                        continue;
                    }

                    if (d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                        p[i][j] = p[k][j];
                    }

                }
            }
        }
        return p;
    }

    /**
     * Constructs matrix P0
     *
     * @param d matrix of lengths
     * @return P0
     */
    private static int[][] constructInitialMatixOfPredecessors(int[][] d) {
        int[][] p = new int[d.length][d.length];
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {
                    p[i][j] = i;
                } else {
                    p[i][j] = -1;
                }
            }
        }
        return p;
    }

    public GraphProblemresult executeOld(List<EdgeDTO> inputEdgeList) {

        Integer startVertex = null;

        DirectedWeightedMultigraph<String, DefaultWeightedEdge> graph = new DirectedWeightedMultigraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
        DefaultWeightedEdge edge1;
        for (EdgeDTO edgeDTO : inputEdgeList) {
            Integer sourceNode = edgeDTO.getSource();
            Integer targetNode = edgeDTO.getTarget();

            if (targetNode == null) {
                startVertex = sourceNode;
                continue;
            }
            if (sourceNode == null) {
                System.out.println("DPC jak to ????");
            }
            double cost = edgeDTO.getCost();
            graph.addVertex(Integer.toString(sourceNode));
            graph.addVertex(Integer.toString(targetNode));

            edge1 = graph.addEdge(Integer.toString(sourceNode), Integer.toString(targetNode));
            graph.setEdgeWeight(edge1, cost);
        }

        List<DefaultWeightedEdge> resultList = new ArrayList<DefaultWeightedEdge>();
        GraphProblemresult shortestPathResult = new GraphProblemresult();
        FloydWarshallShortestPaths floydWarshall = new FloydWarshallShortestPaths(graph);
        List<GraphPathImpl> shortestPaths = floydWarshall.getShortestPaths(startVertex);
        for (GraphPathImpl path : shortestPaths) {
            resultList.addAll(path.getEdgeList());
            resultList.add(null);
        }

//        shortestPathResult.setShortestPath(resultList);
        shortestPathResult.setGraph(graph);

        return shortestPathResult;
    }

    private void printMatrix(int[][] matrix, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.print("\n");
        }
    }
}
